package tree.递归;

import po.TreeNode;

/**
 * @author songZiHao
 * @version 1.0.0
 * @ClassName N删除二叉搜索树中的节点450.java
 * @Description https://leetcode-cn.com/problems/delete-node-in-a-bst/
 * @createTime 2021年05月06日 19:48:00
 */
public class N删除二叉搜索树中的节点450 {
    public TreeNode deleteNode(TreeNode root, int key) {
        if (root == null) {
            return null;
        }
        //寻找节点
        if (root.val < key) {
            root.right = deleteNode(root.right, key);
        } else if (root.val > key) {
            root.left = deleteNode(root.left, key);
        } else {
            if (root.left == null && root.right == null) {
                root=null;
            } else if (root.right != null) {
                /**
                 * 右子树不为空，就找后继节点
                 * 后继节点寻找方式：当前节点的右子树的往下的最左节点
                 */
                root.val=findBehind(root);
                root.right=deleteNode(root.right,root.val);
            }else {
                /**
                 * 左子树不为空，就找前驱节点.
                 * 前驱节点寻找方式：当前节点的左子树的往下的最右节点
                 */
                root.val=findBefore(root);
                root.left=deleteNode(root.left,root.val);
            }
        }
        return root;
    }

    private int findBefore(TreeNode root) {
        root = root.left;
        while (root.right != null){
            root = root.right;
        }
        return root.val;
    }

    private int findBehind(TreeNode root) {
        root=root.right;
        while (root.left != null){
            root = root.left;
        }
        return root.val;
    }
}
